package com.hh.hot100;

import java.util.Arrays;

/**
 * @Author hanghao
 * @Date 2023/7/5 14:02
 * @Version 1.0
 * 合并区间
 * middle
 */

public class No56 {
    public int[][] merge(int[][] intervals) {
        //1、先根据区间开始位置的大小，将 intervals 排序   使用 lambda 表达式会更加高效
        Arrays.sort(intervals,(nums1, nums2) -> nums1[0] - nums2[0]);
        //2、创建一个新的二维数组，用于保存合并后的区间
        int[][] res = new int[intervals.length][2];
        int index = 0;
        //3、开始合并区间
        for (int i = 0; i < intervals.length; i++) {
            //若是第一个区间，或者当前区间的起始位置 > 结果数组res中最后区间的终止位置（注意，结果数组res中最后区间的下标是 index-1）
            //则不需要将当前区间合并到上一个区间，那么当前区间可以赋值给ret，作为一个新的“合并基底”，将后面满足条件的区间向这个基底合并
            if(i == 0 || intervals[i][0] > res[index - 1][1]) {
                res[index++] = intervals[i];
            }
            else {
                //否则，需要将当前区间合并到结果数组res的最后区间（即res中下标为index-1的区间），此时index不需要变化
                //此时需要改变 ret[index][1]，即ret[index] 数组的右边界可能扩展
                res[index - 1][1] = Math.max(res[index - 1][1], intervals[i][1]);
            }
        }
        //res数组中实际上只有 index 个数组有效，其他都是 (0 , 0)，我们原先设置res长度为 intervals.length，需要将有效部分复制返回！
        return Arrays.copyOf(res,index);
    }
}
